<!doctype html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  
  <meta name="generator" content="Hugo 0.98.0" />

  
  <meta name="description" content="走在通往幸福的路上">
  

  
  <link rel="apple-touch-icon" sizes="180x180" href="https://blog.v5u.win/apple-touch-icon.png">

  
  <link rel="icon" type="image/png" sizes="32x32" href="https://blog.v5u.win/favicon-32x32.png">

  
  <link rel="icon" type="image/png" sizes="16x16" href="https://blog.v5u.win/favicon-16x16.png">

  
  <link rel="manifest" href="https://blog.v5u.win/site.webmanifest">

  
  <link rel="mask-icon" href="https://blog.v5u.win/safari-pinned-tab.svg" color="">

  <meta name="msapplication-TileColor" content="">

  <meta name="theme-color" content="">

  
  <link rel="stylesheet" href="https://blog.v5u.win/css/bootstrap.min.css" />

  
  <title>System 最小堆 | 为吾优</title>
  

  <style>
body {
  min-width: 300px;
}

.custom-navbar {
  margin-bottom: 1em;
  height: 60px;
}

.custom-navbar a {
  display: inline-block; 
  padding: 18px 0;
  margin-right: 1em; 
  font-weight: bold; 
}

.custom-navbar a:hover,
.custom-navbar a:focus {
  text-decoration: none; 
}

@media print {
  .custom-navbar {
    display: none;
  }
}

article {
  padding-bottom: 1em;
}

img {
  max-width: 100%;
}


body {
  background-color: #fff;
}



body {
  color: #212529;
}



a {
  color: #007bff;
}



a:hover,
a:focus {
  color: #0056b3;
}



.custom-navbar {
  background-color: #212529;
}



.custom-navbar a {
  color: rgba(255,255,255,.75);
}



.custom-navbar a:hover,
.custom-navbar a:focus {
  color: rgba(255,255,255,1);
}



.container {
  max-width: 800px;
}





</style>
</head>

<body>
  <nav class="custom-navbar">
  <div class="container">
    
    <a href="/">文章</a>
    
    <a href="/tags/">标签</a>
    
    <a href="/about/">关于</a>
    
    <a href="/index.xml">RSS</a>
    
  </div>
</nav>
  
  <div class="container">
    <article>
      <h1>System 最小堆</h1>
<p><strong>最大—最小堆</strong>是最大层和最小层交替出现的<a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91">二叉树</a>，即最大层结点的子节点属于最小层，最小层结点的子节点属于最大层。 以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。</p>
<p><img src="https://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.3.png" alt="最大堆"></p>
<p><img src="https://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.1.png" alt="最小堆"></p>
<p><a href="https://zh.wikipedia.org/w/index.php?title=%E6%9C%80%E5%A4%A7%E5%A0%86&amp;action=edit&amp;redlink=1">最大堆</a>和<a href="https://zh.wikipedia.org/w/index.php?title=%E6%9C%80%E5%B0%8F%E5%A0%86&amp;action=edit&amp;redlink=1">最小堆</a>是<a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86">二叉堆</a>的两种形式。</p>
<ul>
<li>最大堆：根结点的键值是所有堆结点键值中最大者的堆。</li>
<li>最小堆：根结点的键值是所有堆结点键值中最小者的堆。</li>
</ul>
<p>而最大—最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。</p>
<h2 id="主要操作">主要操作</h2>
<h3 id="插入">插入</h3>
<p>将节点插在二叉树的最后一个叶子结点位置，然后比较它与它父亲节点的大小：如果大则停止；如果小则交换位置，然后对父亲节点递归该过程直至根节点。复杂度为{\displaystyle O(log(n))}<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c0bedb281b1771b1dad14e5916d4979f3b57c6b8" alt="{\displaystyle O(log(n))}">。</p>
<p>一般来说，插入的位置可以不是最后一个叶子节点，可以作为任意中间节点的孩子节点插入，将这个叶子节点变为中间节点后，按上文所说的方法调整节点顺序以保证维持堆特性不变。</p>
<h3 id="删除">删除</h3>
<p>要从堆中删除一个节点，用最后一个节点替换掉要删除的节点，然后调整节点顺序以维持堆特性。</p>
<h2 id="应用">应用</h2>
<ul>
<li><a href="https://zh.wikipedia.org/w/index.php?title=%E5%8F%8C%E7%AB%AF%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97&amp;action=edit&amp;redlink=1">双端优先队列</a></li>
</ul>

    </article>
  </div>

  
  
  

  
</body>

</html>